#include "comm/my_rbtree.h"
#include "comm/my_log.h"

typedef struct {
    my_rbtree_node_t    tree_node;
    int                 key;
    int                 val;
} my_test_item_t;

static int
my_test_item_cmp(my_rbtree_node_t *a, my_rbtree_node_t *b) {
    my_test_item_t *anode, *bnode;
    anode = (my_test_item_t *)a;
    bnode = (my_test_item_t *)b;

    if (anode->key == bnode->key) {
        return 0;
    }

    if (anode->key > bnode->key) {
        return 1;
    }

    return -1;
}

void
test_rbtree() {
    my_rbtree_t tree;
    my_rbtree_node_t sentinel;
    my_rbtree_init(&tree, &sentinel, my_test_item_cmp);

    my_test_item_t items[20];

    for (int i = 0; i < 20; i++) {
        items[i].key = 2*i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    for (int i = 0; i < 20; i++) {
        my_test_item_t target = {.key = 2*i};
        my_rbtree_node_t *res = my_rbtree_lookup(&tree, &target.tree_node);
        if (!res) {
            MY_LOG_FATAL("lookup %d failed", target.key);
        }

        my_test_item_t *t = (my_test_item_t *)res;
        if (t->key != 2*i) {
            MY_LOG_FATAL("except %d, but got %d", 2*i, t->key);
        }
    }

    my_rbtree_node_t *tmp;
    for (int i = 0; i < 20; i++) {
        my_test_item_t target = {.key = 2*i};
        tmp = my_rbtree_lookup(&tree, &target.tree_node);
        my_rbtree_delete(&tree, tmp);
    }

    if (!my_rbtree_empty(&tree)) {
        MY_LOG_FATAL("except true, but got false");
    }

    for (int i = 0; i < 20; i++) {
        items[i].key = 2*i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    for (int i = 0; i < 20; i++) {
        my_test_item_t target = {.key = 0};
        my_rbtree_node_t *res = my_rbtree_ge(&tree, &target.tree_node);
        if (!res) {
            MY_LOG_FATAL("lookup %d failed", target.key);
        }

        my_test_item_t *t = (my_test_item_t *)res;
        if (t->key != 2*i) {
            MY_LOG_FATAL("except %d, but got %d", 2*i, t->key);
        }

        my_rbtree_delete(&tree, res);
    }

    if (!my_rbtree_empty(&tree)) {
        MY_LOG_FATAL("except true, but got false");
    }

    for (int i = 0; i < 20; i++) {
        items[i].key = 2*i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    for (int i = 19; i >= 0; i--) {
        my_test_item_t target = {.key = 20*2};
        my_rbtree_node_t *res = my_rbtree_le(&tree, &target.tree_node);
        if (!res) {
            MY_LOG_FATAL("lookup %d failed", target.key);
        }

        my_test_item_t *t = (my_test_item_t *)res;
        if (t->key != 2*i) {
            MY_LOG_FATAL("except %d, but got %d", 2*i, t->key);
        }

        my_rbtree_delete(&tree, res);
    }

    if (!my_rbtree_empty(&tree)) {
        MY_LOG_FATAL("except true, but got false");
    }

    // other
    for (int i = 0; i < 20; i++) {
        items[i].key = 2*i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    my_test_item_t target = {.key = -1};
    if (my_rbtree_lookup(&tree, &target.tree_node)) {
        MY_LOG_FATAL("except NULL, but got other");
    }

    if (my_rbtree_le(&tree, &target.tree_node)) {
        MY_LOG_FATAL("except NULL, but got other");
    }

    target.key = 20 * 2 + 1;
    if (my_rbtree_lookup(&tree, &target.tree_node)) {
        MY_LOG_FATAL("except NULL, but got other");
    }

    if (my_rbtree_ge(&tree, &target.tree_node)) {
        MY_LOG_FATAL("except NULL, but got other");
    }
}

void test_rbtree_same_key() {
    my_rbtree_t tree;
    my_rbtree_node_t sentinel;
    my_rbtree_init(&tree, &sentinel, my_test_item_cmp);

    my_test_item_t items[20];
    for (int i = 0; i < 10; i++) {
        items[i].key = 1;
        items[i].val = i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    for (int i = 10; i < 20; i++) {
        items[i].key = 2;
        items[i].val = i;
        my_rbtree_insert(&tree, &items[i].tree_node);
    }

    for (int i = 0; i < 20; i++) {
        my_rbtree_node_t *node = my_rbtree_min(tree.root, tree.sentinel);
        if (node == NULL) {
            MY_LOG_FATAL("except not NULL");
        }

        my_test_item_t *item = (my_test_item_t *)node;
        if (i < 10) {
            if (item->key != 1) {
                MY_LOG_FATAL("except 1, but got %d", item->key);
            }
            MY_LOG_DEBUG("get item->key: %d, item->value: %d",item->key, item->val);
        } else {
            if (item->key != 2) {
                MY_LOG_FATAL("except 2, but got %d", item->key);
            }
            MY_LOG_DEBUG("get item->key: %d, item->value: %d", item->key, item->val);
        }

        my_rbtree_delete(&tree, node);
    }

    if (!my_rbtree_empty(&tree)) {
        MY_LOG_FATAL("except true, but got false");
    }
}

int main() {
    test_rbtree();
    test_rbtree_same_key();

    MY_LOG_DEBUG("test pass");
    return 0;
}